import math


class Solution(object):
    def largestNumber(self, cost, target):
        d = {}
        for i in range(9):
            d[cost[i]] = i + 1
        d_value = {d[key]: key for key in d}
        min_cost = min(cost)
        max_cost = max(cost)
        value_list = list(d_value.keys())
        value_list.sort(reverse=True)
        cost_list = [d_value[key] for key in value_list]
        m = len(value_list)
        # max_list = [0] * m
        # min_list = [0] * m
        # for i in range(m - 1, -1, -1):
        #     if i == m - 1:
        #         max_list[i] = cost_list[i]
        #         min_list[i] = cost_list[i]
        #     else:
        #         max_list[i] = max(cost_list[i], max_list[i + 1])
        #         min_list[i] = min(cost_list[i], min_list[i + 1])
        max_wei = target // min_cost
        min_wei = target // max_cost

        def dfs(val, t, i):
            if i == m - 1:
                if cost_list[i] * t == val:
                    used.append(t)
                    return True
                else:
                    return False
            else:
                max_num = val // cost_list[i]
                for num in range(min(max_num, t), -1, -1):
                    used.append(num)
                    if dfs(val - num * cost_list[i], t - num, i + 1):
                        return True
                    used.pop()
                return False

        for k in range(max_wei, min_wei - 1, -1):
            used = []
            if dfs(target, k, 0):
                ans = []
                for i in range(m):
                    ans.append(used[i] * str(value_list[i]))
                return ''.join(ans)

        return '0'


data = Solution()
cost = [7, 6, 5, 5, 5, 6, 8, 7, 8]
target = 12
print(data.largestNumber(cost, target))
